package dynamicProgramming

import "fmt"

// 背包问题升级版
// 在背包承重和物品总重最大前提下，引入物品价值变量
// 对于一组不同重量，不同价值，不可分割的物品，如何选择哪些物品放入背包
// 在满足背包最大重量限制前提下，背包中可装入物品的总价值最大是多少呢

// items 依然表示对应物品重量
// values 表示每个物品的价值
// n 表示物品个数 ，w表示背包最大承重

func KnapsackValue(weights, values []int, n, w int) (int, []int) {
	states := make([][]int, n)
	for i := 0; i < n; i++ {
		states[i] = make([]int, w+1)
		// 表格中每个节点初始为负价值
		for j := 0; j < w+1; j++ {
			states[i][j] = -1
		}
	}
	// 特殊处理一个物品
	states[0][0] = 0
	if weights[0] <= w {
		// 第一个物品放入背包，且记录当前总价值
		states[0][weights[0]] = values[0]
	}

	// 计算每一个阶段的状态转移表
	for i := 1; i < n; i++ {
		// 不放入第i个物品，复制上一个阶段的状态转移表
		for j := 0; j <= w; j++ {
			if states[i-1][j] >= 0 {
				// 当前阶段物品价值和上一阶段保持一致
				states[i][j] = states[i-1][j]
			}
		}

		// 第i个物品放入背包
		for j := 0; j <= w-weights[i]; j++ {
			if states[i-1][j] >= 0 {
				v := states[i-1][j] + values[i] // 计算物品价值
				// j+weights[i] == 当前背包中物品总重+当前物品重量
				if v > states[i][j+weights[i]] {
					// 只记录最大值
					states[i][j+weights[i]] = v
				}
			}
		}
	}

	fmt.Println("####状态转移表####")
	fmt.Println(states[n-1])

	// 找到物品最大价值
	maxValue := -1
	maxW := 0
	for j := 0; j <= w; j++ {
		if states[n-1][j] > maxValue {
			maxValue = states[n-1][j]
			maxW = j
		}
	}

	// 找个每个物品决策序列
	// TODO fix??
	items := make([]int, n)
	currentW := maxW
	for i := n - 1; i >= 1; i-- {
		for j := currentW; j >= 0; j-- {
			if states[i][j] >= 0 {
				if j-weights[i] >= 0 {
					items[i] = 1
					currentW -= weights[i]
				} else {
					items[i] = 0
				}
				break
			}
		}
	}

	if currentW == weights[0] {
		items[0] = 1
	}

	return maxValue, items
}

// 优化版本
func KnapsackValue2(weights, values []int, n, w int) int {
	states := make([]int, w+1)
	for k := 0; k < w+1; k++ {
		states[k] = -1
	}

	// 特殊处理第0个物品
	states[0] = 0
	if weights[0] <= w {
		states[weights[0]] = values[0]
	}

	for i := 1; i < n; i++ {
		// j必须从大到小，否则for循环会重复计算分值
		for j := w - weights[i]; j >= 0; j-- {
			if states[j] >= 0 {
				// 第i个物品不放入背包
				// 不做任何记录，和上一个阶段保持一致

				// 第i个物品放入背包
				v := states[j] + values[i]
				if v > states[j+weights[i]] {
					states[j+weights[i]] = v
				}
			}
		}
	}
	fmt.Println("####状态转移表####")
	fmt.Println(states)

	// 寻找最大物品最大价值
	maxV := -1
	maxW := -1
	for j := w; j >= 0; j-- {
		if states[j] > maxV {
			maxV = states[j]
			maxW = j
		}
	}
	fmt.Println("maxW==", maxW)
	fmt.Println("maxV==", maxV)

	// 最优解情况下找一种物品选择方案
	// TODO fix ??
	items := make([]int, n)
	currentW := maxW
	currentV := maxV
	for i := n - 1; i >= 1; i-- {
		if states[currentW-weights[i]] == currentV-values[i] {
			items[i] = 1
			currentV -= values[i]
			currentW -= weights[i]
		}
	}
	if currentW == weights[0] {
		items[0] = 1
	}
	fmt.Println("items==", items)
	return maxV
}
